<!doctype html>
<html lang="zh-cn">
<head>

    <meta charset="utf-8">
    <meta name="generator" content="Hugo 0.57.2" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1">

    <title>HashMap学习 | The Sky of OtsWang</title>
    <meta property="og:title" content="HashMap学习 - The Sky of OtsWang">
    <meta property="og:type" content="article">
        
    <meta property="article:published_time" content="2019-06-04T19:26:28&#43;08:00">
        
        
    <meta property="article:modified_time" content="2019-06-04T19:26:28&#43;08:00">
        
    <meta name="Keywords" content="golang,go语言,otswang,java,博客,python">
    <meta name="description" content="HashMap学习">
        
    <meta name="author" content="OtsWang">
    <meta property="og:url" content="https://otswang.gitee.io/hugo/post/algorithm/hashmap/">
    <link rel="shortcut icon" href="/favicon.ico" type="image/x-icon">

    <link rel="stylesheet" href="/hugo/css/normalize.css">
    
        <link rel="stylesheet" href="/hugo/css/prism.css">
    
    <link rel="stylesheet" href="/hugo/css/style.css">
    <script type="text/javascript" src="//cdn.bootcss.com/jquery/3.2.1/jquery.min.js"></script>

    


    
    
</head>

<body>
<header id="header" class="clearfix">
    <div class="container">
        <div class="col-group">
            <div class="site-name ">
                
                    <a id="logo" href="https://otswang.gitee.io/hugo/">
                        The Sky of OtsWang
                    </a>
                
                <p class="description">擅长写HelloWorld的小小码农</p>
            </div>
            <div>
                <nav id="nav-menu" class="clearfix">
                    
                    
                    <a  href="https://otswang.gitee.io/hugo/" title="Home">Home</a>
                    
                    <a  href="https://otswang.gitee.io/hugo/tags/" title="Tags">Tags</a>
                    
                    <a  href="https://otswang.gitee.io/hugo/categories/" title="Categories">Categories</a>
                    
                    <a  href="https://otswang.gitee.io/hugo/archives/" title="Archives">Archives</a>
                    
                    <a  href="https://otswang.gitee.io/hugo/about/" title="About">About</a>
                    
                </nav>
            </div>
        </div>
    </div>
</header>


<div id="body">
    <div class="container">
        <div class="col-group">

            <div class="col-8" id="main">
                <div class="res-cons">
                    <article class="post">
                        <header>
                            <h1 class="post-title">HashMap学习</h1>
                        </header>
                        <date class="post-meta meta-date">
                            2019年6月4日
                        </date>
                        
                        <div class="post-meta">
                            <span>|</span>
                            
                                <span class="meta-category"><a href="https://otswang.gitee.io/hugo/categories/algorithm">Algorithm</a></span>
                            
                        </div>
                        
                        
                        
                        <div class="post-content">
                            <p>Java面试中经常遇到的一个集合类，实现了接口<code>Map</code>。</p>

<h2 id="原理">原理</h2>

<p>HashMap底层是基于散列算法中的拉链式实现的（另一种是散列再探测），并在jdk1.8中引入红黑树来优化过长的链表。数据结构如下：</p>

<p><img src="/hugo/src/img/algorithm/hashmap.webp" /></p>

<p>数据结构由数组和链表（+树形结构）组成，在进行增删改查时，首先定位到元素所在桶的位置，然后再从链表中定位该元素。</p>

<h2 id="构造方法">构造方法</h2>

<p>参数最多的一个构造方法是：</p>

<pre><code class="language-java">public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity &lt; 0)
        throw new IllegalArgumentException(&quot;Illegal initial capacity: &quot; +
                                           initialCapacity);
    if (initialCapacity &gt; MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor &lt;= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException(&quot;Illegal load factor: &quot; +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
</code></pre>

<p><strong>几个重要参数</strong></p>

<table>
<thead>
<tr>
<th>名称</th>
<th>用途</th>
</tr>
</thead>

<tbody>
<tr>
<td>initialCapacity</td>
<td>HashMap的初始容量</td>
</tr>

<tr>
<td>loadFactor</td>
<td>负载因子</td>
</tr>

<tr>
<td>threshhold</td>
<td>所能容纳键值对的最大值，超过则需扩容</td>
</tr>
</tbody>
</table>

<pre><code class="language-java">/** The default initial capacity - MUST be a power of two. */
static final int DEFAULT_INITIAL_CAPACITY = 1 &lt;&lt; 4;

/** The load factor used when none specified in constructor. */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

final float loadFactor;

/** The next size value at which to resize (capacity * load factor). */
int threshold;
</code></pre>

<pre><code class="language-java">/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n &gt;&gt;&gt; 1;
    n |= n &gt;&gt;&gt; 2;
    n |= n &gt;&gt;&gt; 4;
    n |= n &gt;&gt;&gt; 8;
    n |= n &gt;&gt;&gt; 16;
    return (n &lt; 0) ? 1 : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
</code></pre>

<p>此方法比较复杂，但是功能比较简单，就是找出比cap大的最小2的幂。</p>

<p>说下负载因子，如果负载因子很小，则在扩容时，健之间的碰撞会变小，增删改查的效率会提高不少，这是以空间换时间。同理，当负载因子大时，是使用时间换空间。</p>

<pre><code class="language-java">public V get(Object key) {
    Node&lt;K,V&gt; e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node&lt;K,V&gt; getNode(int hash, Object key) {
    Node&lt;K,V&gt;[] tab;        // table
    Node&lt;K,V&gt; first, e; 
    int n;                  // length of table
    K k;
    // 1. 定位键值对所在桶的位置
    if ((tab = table) != null &amp;&amp; (n = tab.length) &gt; 0 &amp;&amp;
        (first = tab[(n - 1) &amp; hash]) != null) {
        if (first.hash == hash &amp;&amp; // always check first node
            ((k = first.key) == key || (key != null &amp;&amp; key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 2. 如果 first 是 TreeNode 类型，则调用黑红树查找方法
            if (first instanceof TreeNode)
                return ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);
                
            // 2. 对链表进行查找
            do {
                if (e.hash == hash &amp;&amp;
                    ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
</code></pre>

<p><code>(n-1) &amp; hash</code>等价于对n取余。(原理可以多想一下，很巧妙)</p>

<pre><code class="language-java">/**
 * 计算键的 hash 值
 * int 值占4字节，共32位
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16);
}
</code></pre>

<h2 id="遍历">遍历</h2>

<pre><code class="language-java">public Set&lt;K&gt; keySet() {
    Set&lt;K&gt; ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

/**
 * 键集合
 */
final class KeySet extends AbstractSet&lt;K&gt; {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator&lt;K&gt; iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    // 省略部分代码
}

/**
 * 键迭代器
 */
final class KeyIterator extends HashIterator 
    implements Iterator&lt;K&gt; {
    public final K next() { return nextNode().key; }
}

abstract class HashIterator {
    Node&lt;K,V&gt; next;        // next entry to return
    Node&lt;K,V&gt; current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        Node&lt;K,V&gt;[] t = table;
        current = next = null;
        index = 0;
        if (t != null &amp;&amp; size &gt; 0) { // advance to first entry 
            // 寻找第一个包含链表节点引用的桶
            do {} while (index &lt; t.length &amp;&amp; (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Node&lt;K,V&gt; nextNode() {
        Node&lt;K,V&gt;[] t;
        Node&lt;K,V&gt; e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null &amp;&amp; (t = table) != null) {
            // 寻找下一个包含链表节点引用的桶
            do {} while (index &lt; t.length &amp;&amp; (next = t[index++]) == null);
        }
        return e;
    }
    //省略部分代码
}
</code></pre>

<h2 id="插入">插入</h2>

<p>首先肯定是先定位要插入的键值对属于哪个桶，定位到桶后，再判断桶是否为空。如果为空，则将键值对存入即可。如果不为空，则需将键值对接在链表最后一个位置，或者更新键值对。</p>

<p>在jdk1.8后，需要将长链表优化为红黑树。</p>

<pre><code class="language-java">public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; int n, i;
    // 初始化桶数组 table，table 被延迟到插入新数据时再进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果桶中不包含键值对节点引用，则将新键值对节点的引用存入桶中即可
    if ((p = tab[i = (n - 1) &amp; hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node&lt;K,V&gt; e; K k;
        // 如果键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对
        if (p.hash == hash &amp;&amp;
            ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))
            e = p;
            
        // 如果桶中的引用类型为 TreeNode，则调用红黑树的插入方法
        else if (p instanceof TreeNode)  
            e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 对链表进行遍历，并统计链表长度
            for (int binCount = 0; ; ++binCount) {
                // 链表中不包含要插入的键值对节点时，则将该节点接在链表的最后
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果链表长度大于或等于树化阈值，则进行树化操作
                    if (binCount &gt;= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                
                // 条件为 true，表示当前链表包含要插入的键值对，终止遍历
                if (e.hash == hash &amp;&amp;
                    ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 判断要插入的键值对是否存在 HashMap 中
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 键值对数量超过阈值时，则进行扩容
    if (++size &gt; threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
</code></pre>

<h2 id="扩容">扩容</h2>

<p>HashMap 按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）。扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去。</p>

<pre><code class="language-java">final Node&lt;K,V&gt;[] resize() {
    Node&lt;K,V&gt;[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果 table 不为空，表明已经初始化过了
    if (oldCap &gt; 0) {
        // 当 table 容量超过容量最大值，则不再扩容
        if (oldCap &gt;= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } 
        // 按旧容量和阈值的2倍计算新容量和阈值的大小
        else if ((newCap = oldCap &lt;&lt; 1) &lt; MAXIMUM_CAPACITY &amp;&amp;
                 oldCap &gt;= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr &lt;&lt; 1; // double threshold
    } else if (oldThr &gt; 0) // initial capacity was placed in threshold
        /*
         * 初始化时，将 threshold 的值赋值给 newCap，
         * HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值
         */ 
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        /*
         * 调用无参构造方法时，桶数组容量为默认容量，
         * 阈值为默认容量与默认负载因子乘积
         */
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // newThr 为 0 时，按阈值计算公式进行计算
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 创建新的桶数组，桶数组的初始化也是在这里完成的
    Node&lt;K,V&gt;[] newTab = (Node&lt;K,V&gt;[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 如果旧的桶数组不为空，则遍历桶数组，并将键值对映射到新的桶数组中
        for (int j = 0; j &lt; oldCap; ++j) {
            Node&lt;K,V&gt; e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash &amp; (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 重新映射时，需要对红黑树进行拆分
                    ((TreeNode&lt;K,V&gt;)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node&lt;K,V&gt; loHead = null, loTail = null;
                    Node&lt;K,V&gt; hiHead = null, hiTail = null;
                    Node&lt;K,V&gt; next;
                    // 遍历链表，并将链表节点按原顺序进行分组
                    do {
                        next = e.next;
                        if ((e.hash &amp; oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 将分组后的链表映射到新桶中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
</code></pre>

<h2 id="删除">删除</h2>

<pre><code class="language-java">public V remove(Object key) {
    Node&lt;K,V&gt; e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node&lt;K,V&gt; removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; int n, index;
    if ((tab = table) != null &amp;&amp; (n = tab.length) &gt; 0 &amp;&amp;
        // 1. 定位桶位置
        (p = tab[index = (n - 1) &amp; hash]) != null) {
        Node&lt;K,V&gt; node = null, e; K k; V v;
        // 如果键的值与链表第一个节点相等，则将 node 指向该节点
        if (p.hash == hash &amp;&amp;
            ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {  
            // 如果是 TreeNode 类型，调用红黑树的查找逻辑定位待删除节点
            if (p instanceof TreeNode)
                node = ((TreeNode&lt;K,V&gt;)p).getTreeNode(hash, key);
            else {
                // 2. 遍历链表，找到待删除节点
                do {
                    if (e.hash == hash &amp;&amp;
                        ((k = e.key) == key ||
                         (key != null &amp;&amp; key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        
        // 3. 删除节点，并修复链表或红黑树
        if (node != null &amp;&amp; (!matchValue || (v = node.value) == value ||
                             (value != null &amp;&amp; value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode&lt;K,V&gt;)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}
</code></pre>

<h2 id="一个细节">一个细节</h2>

<p>如果大家细心阅读 HashMap 的源码，会发现桶数组 table 被申明为 transient。transient 表示易变的意思，在 Java 中，被该关键字修饰的变量不会被默认的序列化机制序列化。我们再回到源码中，考虑一个问题：桶数组 table 是 HashMap 底层重要的数据结构，不序列化的话，别人还怎么还原呢？</p>

<p>其实HashMap 并没有使用默认的序列化机制，而是通过实现readObject/writeObject两个方法自定义了序列化的内容。这样做是有原因的，试问一句，HashMap 中存储的内容是什么？是键值对。所以只要我们把键值对序列化了，我们就可以根据键值对数据重建 HashMap。有的朋友可能会想，序列化 table 不是可以一步到位，后面直接还原不就行了吗？这样一想，倒也是合理。但序列化 talbe 存在着两个问题：</p>

<ol>
<li>table 多数情况下是无法被存满的，序列化未使用的部分，浪费空间</li>
<li>同一个键值对在不同 JVM 下，所处的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能会发生错误。</li>
</ol>

<p>以上两个问题中，第一个问题比较好理解，第二个问题解释一下。HashMap 的get/put/remove等方法第一步就是根据 hash 找到键所在的桶位置，但如果键没有覆写 hashCode 方法，计算 hash 时最终调用 Object 中的 hashCode 方法。但 <strong>Object 中的 hashCode 方法是 native 型的</strong>，不同的 JVM 下，可能会有不同的实现，产生的 hash 可能也是不一样的。也就是说同一个键在不同平台下可能会产生不同的 hash，此时再对在同一个 table 继续操作，就会出现问题。</p>

<blockquote>
<p>参考内容:</p>

<p><a href="https://segmentfault.com/a/1190000012926722#articleHeader0">HashMap 源码详细分析(JDK1.8)</a></p>
</blockquote>
                        </div>

                        


                        

<div class="post-archive">
    <h2>See Also</h2>
    <ul class="listing">
        
        <li><a href="/hugo/post/java/multithread/">Java多线程</a></li>
        
        <li><a href="/hugo/post/java/thinking_in_java/%E7%AC%AC%E4%BA%8C%E5%8D%81%E7%AB%A0-%E6%B3%A8%E8%A7%A3/">第二十章 注解</a></li>
        
        <li><a href="/hugo/post/java/thinking_in_java/%E7%AC%AC%E5%8D%81%E5%85%AB%E7%AB%A0-java-io%E7%B3%BB%E7%BB%9F/">第十八章 Java IO系统</a></li>
        
        <li><a href="/hugo/post/java/thinking_in_java/%E7%AC%AC%E5%8D%81%E4%B8%83%E7%AB%A0-%E5%AF%B9%E8%B1%A1%E7%9A%84%E5%AE%B9%E7%BA%B3-%E5%AE%B9%E5%99%A8/">第十七章 对象的容纳-容器</a></li>
        
        <li><a href="/hugo/post/java/thinking_in_java/%E7%AC%AC%E5%85%AB%E7%AB%A0-%E5%A4%9A%E6%80%81%E6%80%A7/">第八章 多态性</a></li>
        
    </ul>
</div>


                        <div class="post-meta meta-tags">
                            
                            <ul class="clearfix">
                                
                                <li><a href="https://otswang.gitee.io/hugo/tags/java">Java</a></li>
                                
                                <li><a href="https://otswang.gitee.io/hugo/tags/map">Map</a></li>
                                
                            </ul>
                            
                        </div>
                    </article>
                    
    

    
    
                </div>
            </div>
            <div id="secondary">

    <section class="widget">
        <form id="search" action="//www.google.com/search" method="get" accept-charset="utf-8" target="_blank" _lpchecked="1">
      
      <input type="text" name="q" maxlength="20" placeholder="Search">
      <input type="hidden" name="sitesearch" value="https://otswang.gitee.io/hugo/">
      <button type="submit" class="submit icon-search"></button>
</form>
    </section>

    
    <div class="clear">
        <div class="toc-article">
            <div class="toc-title">文章目录</dixsv>
            <nav id="TableOfContents">
<ul>
<li>
<ul>
<li><a href="#原理">原理</a></li>
<li><a href="#构造方法">构造方法</a></li>
<li><a href="#遍历">遍历</a></li>
<li><a href="#插入">插入</a></li>
<li><a href="#扩容">扩容</a></li>
<li><a href="#删除">删除</a></li>
<li><a href="#一个细节">一个细节</a></li>
</ul></li>
</ul>
</nav>
        </div>
    </div>
    

</div>
        </div>
    </div>
</div>
<footer id="footer">
    <div class="container">
        &copy; 2020 <a href="https://otswang.gitee.io/hugo/">The Sky of OtsWang By OtsWang</a>.
        Powered by <a rel="nofollow noreferer noopener" href="https://gohugo.io" target="_blank">Hugo</a>.
        <a href="https://www.flysnow.org/" target="_blank">Theme</a> based on <a href="https://github.com/Dudiao137/maupassant-hugo" target="_blank">maupassant-ots</a>.
        
    </div>
</footer>


    <script type="text/javascript">
    
    (function(){
        $("pre code").parent().addClass("line-numbers")
    }())

    window.MathJax = {
        tex2jax: {
            inlineMath: [ ['$','$'] ],
            processEscapes: true
        }
    };
    </script>
    <script type="text/javascript" src="/hugo/js/prism.js" async="true"></script>
    <script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML' async></script>

<a id="rocket" href="#top"></a>
<script type="text/javascript" src="/hugo/js/totop.js?v=0.0.0" async=""></script>







 
 <script src="https://mermaidjs.github.io/scripts/mermaid.min.js"></script>
 <script>
       mermaid.initialize({ startOnLoad: true });
 </script>
</body>
</html>
